一、NetMF [2017]

《Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec》

1. 传统的网络挖掘、网络学习的范式通常从对网络结构属性（structural property） 的显式探索而开始。但是许多这类的属性（如中介中心度 betweenness centrality、三角计数 triangle count、模度 modularity）由人工制作，并且需要广泛的领域知识和昂贵的计算代价。鉴于这些问题，以及最近出现的 representation learning 所提供的机会，人们广泛研究了学习网络的潜在 representation（也就是 network embedding ），以便自动发现网络的结构属性并将其映射到一个潜在的空间。

   形式上，network embedding 的问题通常形式化如下：给定一个无向带权图 $G=(V,E,\mathbf{A})$$G=(V,E,\mathbf A)$ ，其中 $V$$V$ 为顶点集合、$E$$E$ 为边集合、$\mathbf{A}$$\mathbf A$ 为邻接矩阵，任务的目标是学习一个映射 $V\to {\mathbb{R}}^d$$V\rightarrow \mathbb R^d$ ，该映射将每个顶点映射到一个能够捕获该顶点结构属性的 $d$$d$ 维向量。输出的 representation 可以用于各种网络科学任务、网络 learning algorithm 的输入，例如标签分类、社区检测。

   解决这个问题的尝试可以追溯到谱图理论（spectral graph theory） 和社交维度学习（ social dimension learning ）。该问题最近的进展很大程度上受到 SkipGram 模型的影响。SkipGram 模型最初是为 word embedding 所提出的，其输入是由自然语言中的句子组成的文本语料库，输出是语料库中每个单词的 latent vector representation 。值得注意的是，受到该 setting 的启发，DeepWalk 通过将网络上随机游走所遍历的顶点路径视为句子，并利用 SkipGram 来学习潜在的节点 representation，从而开创了 network embedding 的先河。随着 DeepWalk 的出现，人们后续已经开发了很多 network embedding 模型，例如 LINE、PTE、node2vec 。

   到目前为止，上述模型已经被证明非常有效。然而，它们背后的理论机制却鲜为人知。人们注意到，用于 word embedding 的、带负采样的 SkipGram 模型已经被证明是某个 word-context 矩阵的隐式分解，并且最近有人努力从几何角度从理论上解释 word embedding 模型。但是，目前尚不清楚 word-context 矩阵与网络结构之间的关系。此外，早期人们尝试从理论上分析 DeepWalk 的行为，然而他们的主要理论结果和原始 DeepWalk 论文的 setting 并不完全一致。此外，尽管 DeepWalk, LINE, PTE, node2vec 之间存在表面上的相似性，但是对它们的底层联系缺乏更深入的了解。

   在论文 《Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec》中，作者提供了关于几种基于 SkipGram 的 network embedding 方法的理论结果。具体而言：

   • 论文首先表明这里提到的模型（即 DeepWalk, LINE, PTE, node2vec ）在理论上执行隐式矩阵分解。论文为每个模型推导出矩阵的封闭形式（ closed form ）。例如，DeepWalk （图上的随机游走加上 SkipGram）本质上是对一个随机矩阵进行因子分解，并且随着随机游走的长度趋于无穷大，该矩阵在概率上收敛到这个的闭式矩阵。

   • 其次，从它们矩阵的闭式形式观察，作者发现有意思的是，LINE 可以视为 DeepWalk 的一个特例：当 SkipGram 中的上下文窗口大小 $T=1$$T = 1$ 时。此外，作者证明了 PTE 作为 LINE 的扩展，实际上是多网络的联合矩阵（joint matrix） 的隐式分解。

   • 第三，作者发现了 DeepWalk 的隐式矩阵（implicit matrix ）和图拉普拉斯矩阵（graph Laplacian ）之间的理论联系。基于这种联系，作者提出了一种新算法 NetMF 来逼近 DeepWalk 隐式矩阵的封闭形式。通过使用 SVD 显式分解该矩阵，论文在四个网络（在 DeepWalk 和 node2vec 论文中所采用的）中的广泛实验证明了 NetMF 相比于 DeepWalk 和 LINE 的出色性能（相对提升高达 50%）。

   论文的理论价值高于 NetMF 实用的价值，实际上 NetMF 很难应用到工业环境中，因为 NetMF 的时间复杂度和空间复杂度都太高。

2. 论文展示了所有上述带负采样的模型都可以统一到具有封闭形式（closed form ）的矩阵分解框架中。论文的分析和证明表明：

   • DeepWalk 经验性（empirically ）地产生了网络归一化拉普拉斯矩阵的低秩变换（low-rank transformation） 。

   • LINE 理论上是 DeepWalk 的一个特例：当顶点的上下文 size 为 1 时。

   • 作为 LINE 的扩展，PTE 可以视为多个网络的拉普拉斯矩阵的联合分解。

   • node2vec 正在分解与二阶随机游走的平稳分布、转移概率张量等相关的矩阵。

   这项工作为基于 SkipGram 的 network embedding 方法奠定了理论基础，从而更好地理解了潜在的 network representation learning 。

3. 相关工作：network embedding 的故事来源于谱聚类（ Spectral Clustering）。谱聚类是一种数据聚类技术，它选择数据的亲和矩阵（ affinity matrix ）的特征值（eigenvalue ）/特征向量（ eigenvector ）从而获得representation ，从而进一步用于聚类或嵌入到低维空间。谱聚类已广泛应用于社区检测和图像分割等领域。

   近年来，人们对 network embedding 越来越感兴趣。继 SocDim 和 DeepWalk 等一些开创性工作之后，越来越多的文献试图从不同的角度解决这个问题，例如 heterogeneous network embedding 、半监督 network embedding、具有丰富顶点属性的 network embedding、具有高阶结构的 network embedding、有符号的 network embedding 、有向的network embedding、通过神经网络的 network embedding 等等。在上述研究中，一种常用的技术是为每个顶点定义 context，然后训练一个预测模型来进行上下文预测。例如，DeepWalk, node2vec, metapath2vec 分别通过基于一阶的随机游走、基于二阶的随机游走、基于 metapath 的随机游走来定义顶点的上下文。

   利用上下文信息的思想很大程度上是由带负采样的 SkipGram 模型skip-gram model with negative sampling: SGNS所推动的。最近，人们一直在努力理解这个模型。例如：

   • 《NeuralWord Embedding as Implicit Matrix Factorization》 证明了 SGNS 实际上是进行隐式矩阵分解，这为我们提供了分析上述 network embedding 模型的工具。

   • 《A latent variable model approach to pmi-based word embeddings》 提出生成模型 RAND-WALK 来解释 word embedding 模型。

   • 《Word embeddings as metric recovery in semantic spaces》 将 word embedding 框架作为度量学习问题。

   基于隐式矩阵分解的工作，我们从理论上分析了流行的、基于 SkipGram 的 network embedding 模型，并将它们与谱图理论联系起来。

1.1 模型

1. 这里我们首先介绍四种流行的 network embedding 方法（LINE, PTE, DeepWalk, node2vec）的详细理论分析和证明，然后提出我们的 NetMF 方法。

1.1.1 LINE

1. 给定一个带权无向图 $G=(V,E,\mathbf{A})$$G=(V,E,\mathbf A)$，二阶邻近性的LINE（即 LINE(2nd) ）的任务是学到两个representation 矩阵 ：

   • vertex represetation 矩阵 $\mathbf{X}\in {\mathbb{R}}^{|V|\times d}$$\mathbf X \in \mathbb R^{|V|\times d}$：第 $i$$i$ 行 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 为顶点 $v_i$$v_i$ 作为vertex 时的 embedding 向量。

   • context representation 矩阵$\mathbf{Y}\in {\mathbb{R}}^{|V|\times d}$$\mathbf Y \in \mathbb R^{|V|\times d}$ ：第 $i$$i$ 行 ${\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec y}_i$ 为顶点 $v_i$$v_i$ 作为contex 时的 embedding 向量。

   LINE(2nd) 的目标函数为：

   $$\mathcal{L}=\sum _{i=1}^{|V|}\sum _{j=1}^{|V|}{A}_{i,j}(\log \sigma ({\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j)+b{\mathbb{E}}_{j^{\prime }\sim P_N}[\log \sigma (-{\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_{j^{\prime }})])$$

   其中：$\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 函数，$b$$b$ 为负采样系数，$P_N$$P_N$ 为用于产生负样本的 noise 分布。在 LINE 原始论文中使用经验分布 $P_N(j)\propto d_j^{3/4}$$P_N(j)\propto d_j^{3/4}$ ，其中 $d_j$$d_j$ 为顶点 $j$$j$ 的加权 degree $d_j=\sum _{k=1}^{|V|}{A}_{j,k}$$d_j = \sum_{k=1}^{|V|}A_{j,k}$ 。

   LINE(2nd) 的目标函数为 $-\sum _{(i,j)\in E}{A}_{i,j}\times \log \frac{\exp ({\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j)}{\sum _{k=1}^{|V|}\exp ({\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_k)}$$-\sum_{(i,j)\in E} A_{i,j}\times \log \frac{\exp(\mathbf{\vec x}_i\cdot \mathbf{\vec y}_j)}{\sum_{k=1}^{|V|}\exp(\mathbf{\vec x}_i\cdot \mathbf{\vec y}_k)}$ （即 $-\sum _{(i,j)\in E}{A}_{i,j}\times \log p_2(v_j\mid v_i)$$-\sum_{(i,j)\in E} A_{i,j}\times \log p_2(v_j\mid v_i)$），考虑到 $(i,j)\notin E$$(i,j)\notin E$ 时 $A_{i,j}=0$$A_{i,j} = 0$ 以及负采样，则得到上述目标函数。这也是为什么 $\mathcal{L}$$\mathcal L$ 中 $A_{i,j}$$A_{i,j}$ 不仅作用在“正边”、也作用在 “负边” 上的原因。

2. 本文我们选择 $P_N(j)\propto d_j$$P_N(j)\propto d_j$ ，因为这种形式的经验分布将得到一个闭式解（closed form solution） 。定义 ${\text{vol}}_G=\sum _{i=1}^{|V|}\sum _{j=1}^{|V|}{A}_{i,j}=\sum _{j=1}^{|V|}{d}_j$$\text{vol}_G = \sum_{i=1}^{|V|}\sum_{j=1}^{|V|}A_{i,j}=\sum_{j=1}^{|V|}d_j$ 为所有顶点的加权 degree 之和，则有 $P_N(j)=\frac{d_j}{{\text{vol}}_G}$$P_N(j) = \frac{d_j}{\text{vol}_G}$ 。我们重写目标函数为：

   $$\mathcal{L}=(\sum _{i=1}^{|V|}\sum _{j=1}^{|V|}{A}_{i,j}\log \sigma ({\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j))+(b\sum _{i=1}^{|V|}{d}_i{\mathbb{E}}_{j^{\prime }\sim P_N}[\log \sigma (-{\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_{j^{\prime }})])$$

   我们在图 $G$$G$ 的所有顶点上计算，从而得到期望为：

   $${\mathbb{E}}_{j^{\prime }\sim P_N}[\log \sigma (-{\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_{j^{\prime }})]=\sum _{j=1}^{|V|}\frac{d_j}{{\text{vol}}_G}\log \sigma (-{\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j)$$

   因此有：

   $$\mathcal{L}=\sum _{i=1}^{|V|}\sum _{j=1}^{|V|}(A_{i,j}\log \sigma ({\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j)+b\frac{d_i{d}_j}{{\text{vol}}_G}\log \sigma ({\mathbf{-}\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j))$$

   则对于每一对顶点 (i,j)，其局部目标函数（local objective function ）为：

   $$\mathcal{L}(i,j)=A_{i,j}\log \sigma ({\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j)+b\frac{d_i{d}_j}{{\text{vol}}_G}\log \sigma ({\mathbf{-}\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j)$$

   定义 $z_{i,j}={\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j$$z_{i,j} = \mathbf{\vec x}_i \cdot \mathbf{\vec y}_j$ ，根据 《NeuralWord Embedding as Implicit Matrix Factorization》 的结论：对于一个足够大的 embedding 维度， 每个 $z_{i,j}$$z_{i,j}$ 之间可以认为是相对独立的。因此我们有：

   $$\frac{\partial \mathcal{L}}{\partial z_{i,j}}=\frac{\partial \mathcal{L}(i,j)}{\partial z_{i,j}}=A_{i,j}\sigma (-z_{i,j})-b\frac{d_i{d}_j}{{\text{vol}}_G}\sigma (z_{i,j})$$

   为求解目标函数极大值，我们令偏导数为零，则有：

   $$\exp (2z_{i,j})-(\frac{{\text{vol}}_G{A}_{i,j}}{b{d}_i{d}_j}-1)\exp (z_{i,j})-\frac{{\text{vol}}_G{A}_{i,j}}{b{d}_i{d}_j}=0$$

   这个方程有两个闭式解：

   • $\exp (z_{i,j})=-1$$\exp(z_{i,j}) = -1$ ：其解为虚数，不予考虑。

   • $\exp (z_{i,j})=\frac{{\text{vol}}_G{A}_{i,j}}{b{d}_i{d}_j}$$\exp(z_{i,j}) = \frac{\text{vol}_G A_{i,j}}{bd_id_j}$ ：有效解。

   因此有：

   $${\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j=z_{i,j}=\log \left(\frac{{\text{vol}}_G{A}_{i,j}}{b{d}_i{d}_j}\right)$$

   则 LINE(2nd) 对应于矩阵分解：

   $$\mathbf{X}{\mathbf{Y}}^{\mathrm{\top }}=\log ({\text{vol}}_G{\mathbf{D}}^{-1}\mathbf{A}{\mathbf{D}}^{-1})-(\log b)\mathbf{I}$$

   其中对角矩阵 $\mathbf{D}=\text{diag}(d_1,\cdots ,d_{|V|})$$\mathbf D = \text{diag}(d_1,\cdots,d_{|V|})$。

1.1.2 PTE

1. PTE 是 LINE(2nd) 在异质文本网络heterogeneous text network 中的扩展。我们首先将我们对 LINE(2nd) 的分析调整到二部图网络。考虑一个二部图网络 $G=(V_1\cup V_2,E,\mathbf{A})$$G=(V_1\cup V_2, E, \mathbf A)$，其中 $V_1$$V_1$ 和 $V_2$$V_2$ 是两个不相交的顶点集合，$E\subseteq V_1\times V_2$$E\sube V_1\times V_2$ 是边集合，$\mathbf{A}\in {\mathbb{R}}^{|V_1|\times |V_2|}$$\mathbf A\in \mathbb R^{|V_1|\times |V_2|}$ 为二部图网络的邻接矩阵。定义图 $G$$G$ 的 volume 为 ${\text{vol}}_G=\sum _{i=1}^{|V_1|}\sum _{j=1}^{|V_2|}{A}_{i,j}$$\text{vol}_G = \sum_{i=1}^{|V_1|}\sum_{j=1}^{|V_2|} A_{i,j}$ 。则 PTE 的目标是学习每个节点 $v_i\in V_1$$v_i\in V_1$ 的节点 representation ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 、以及学习每个节点 $v_j\in V_2$$v_j\in V_2$ 的节点 representation ${\overrightarrow{\mathbf{y}}}_j$$\mathbf{\vec y}_j$ 。则 LINE(2nd) 的目标函数为：

   $$\mathcal{L}=\sum _{i=1}^{|V_1|}\sum _{j=1}^{|V_2|}{A}_{i,j}(\log \sigma ({\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j)+b{\mathbb{E}}_{j^{\prime }\sim P_N}[\log \sigma (-{\overrightarrow{\mathbf{x}}}_i\cdot {\overrightarrow{\mathbf{y}}}_{j^{\prime }})])$$

   这里 $V_1$$V_1$ 内节点和 $V_2$$V_2$ 内节点互为上下文，因此没必要引入 $V_1$$V_1$ 上下文的 embedding 变量、$V_2$$V_2$ 上下文的 embedding 变量。

   与 LINE 相同的分析过程，我们可以发现最大化 $\mathcal{L}$$\mathcal L$ 等价于因子分解：

   $$\mathbf{X}{\mathbf{Y}}^{\mathrm{\top }}=\log ({\text{vol}}_G{\mathbf{D}}_{\text{row}}^{-1}\mathbf{A}{\mathbf{D}}_{\text{col}}^{-1})-(\log b)\mathbf{I}$$

   其中 ${\mathbf{D}}_{\text{row}}=\text{diag}(\mathbf{A}\overrightarrow{\mathbf{e}})$$\mathbf D_\text{row} = \text{diag}(\mathbf A\mathbf{\vec e})$ 为 $\mathbf{A}$$\mathbf A$ 各行之和构成的对角矩阵， ${\mathbf{D}}_{\text{col}}=\text{diag}({\mathbf{A}}^{\mathrm{\top }}\overrightarrow{\mathbf{e}})$$\mathbf D_\text{col} = \text{diag}(\mathbf A^\top\mathbf{\vec e})$ 为 $\mathbf{A}$$\mathbf A$ 各列之和构成的对角矩阵，$\overrightarrow{\mathbf{e}}$$\mathbf{\vec e}$ 为全 1 的向量。

   当二部图是无向图时，$\mathbf{A}={\mathbf{A}}^{\mathrm{\top }}$$\mathbf A = \mathbf A^\top$ （无向图的出边就是入边），则 ${\mathbf{D}}_{\text{row}}={\mathbf{D}}_{\text{col}}$$\mathbf D_\text{row} = \mathbf D_\text{col}$ 。

2. 基于上述分析，接下来我们考虑 PTE 中的异质文本网络。假设单词集合为 $\mathbb{V}$$\mathbb V$ ，文档集合为 $\mathbb{D}$$\mathbb D$ ，标签集合为 $\mathbb{L}$$\mathbb L$ ，我们将文本网络分为三个子网络：

   • word-word 子网 $G^{w,w}$$G^{w,w}$：每个 word 是一个顶点，边的权重为两个 word 在大小为 T 的窗口内共现的次数。假设其邻接矩阵为 ${\mathbf{A}}^{w,w}$$\mathbf A^{w,w}$ ，定义 $d_{i\cdot ,}^{w,w}=\sum _j{A}_{i,j}^{w,w}$$d_{i\cdot,}^{w,w} = \sum_j A_{i,j}^{w,w}$ 为 ${\mathbf{A}}^{w,w}$$\mathbf A^{w,w}$ 第 $i$$i$ 行的元素之和， 定义 $d_{\cdot ,j}^{w,w}=\sum _i{A}_{i,j}^{w,w}$$d_{\cdot,j}^{w,w} = \sum_i A_{i,j}^{w,w}$ 为 ${\mathbf{A}}^{w,w}$$\mathbf A^{w,w}$ 第 $j$$j$ 列的元素之和。定义对角矩阵 ${\mathbf{D}}_{\text{row}}^{w,w}=\text{diag}(d_{1,\cdot }^{w,w},\cdots ,d_{|\mathbb{V}|,\cdot }^{w,w})$$\mathbf D_\text{row}^{w,w} = \text{diag}(d^{w,w}_{1,\cdot},\cdots,d^{w,w}_{|\mathbb V|,\cdot})$， ${\mathbf{D}}_{\text{col}}^{w,w}=\text{diag}(d_{\cdot ,1}^{w,w},\cdots ,d_{\cdot ,|\mathbb{V}|}^{w,w})$$\mathbf D_\text{col}^{w,w} = \text{diag}(d^{w,w}_{\cdot,1},\cdots,d^{w,w}_{\cdot,|\mathbb V|})$ ，它们分别由 ${\mathbf{A}}^{w,w}$$\mathbf A^{w,w}$ 的各行之和、各列之和组成。

   • word-document 子网 $G^{d,w}$$G^{d,w}$ ：每个 word 和 document 都是一个顶点，边的权重是word 出现在文档中的次数。同样地我们定义对角矩阵 ${\mathbf{D}}_{\text{row}}^{w,d}=\text{diag}(d_{1,\cdot }^{w,d},\cdots ,d_{|\mathbb{V}|,\cdot }^{w,d})$$\mathbf D_\text{row}^{w,d} = \text{diag}(d^{w,d}_{1,\cdot},\cdots,d^{w,d}_{|\mathbb V|,\cdot})$， ${\mathbf{D}}_{\text{col}}^{w,d}=\text{diag}(d_{\cdot ,1}^{w,d},\cdots ,d_{\cdot ,|\mathbb{D}|}^{w,d})$$\mathbf D_\text{col}^{w,d} = \text{diag}(d^{w,d}_{\cdot,1},\cdots,d^{w,d}_{\cdot,|\mathbb D|})$ ，它们分别由 ${\mathbf{A}}^{w,d}$$\mathbf A^{w,d}$ 的各行之和、各列之和组成。

   • word-label 子网 $G^{w,l}$$G^{w,l}$：每个 word 和 label 都是一个顶点，边的权重为 word 出现在属于这个 label 的文档的篇数。同样的我们定义对角矩阵 ${\mathbf{D}}_{\text{row}}^{w,l}=\text{diag}(d_{1,\cdot }^{w,l},\cdots ,d_{|\mathbb{V}|,\cdot }^{w,l})$$\mathbf D_\text{row}^{w,l} = \text{diag}(d^{w,l}_{1,\cdot},\cdots,d^{w,l}_{|\mathbb V|,\cdot})$， ${\mathbf{D}}_{\text{col}}^{w,l}=\text{diag}(d_{\cdot ,1}^{w,l},\cdots ,d_{\cdot ,|\mathbb{L}|}^{w,l})$$\mathbf D_\text{col}^{w,l} = \text{diag}(d^{w,l}_{\cdot,1},\cdots,d^{w,l}_{\cdot,|\mathbb L|})$ ，它们分别由 ${\mathbf{A}}^{w,d}$$\mathbf A^{w,d}$ 的各行之和、各列之和组成。

   PTE 的损失函数为：

   $$\begin{array}{c}\mathcal{L}=\alpha {\mathcal{L}}_{w,w}+\beta {\mathcal{L}}_{w,d}+\gamma {\mathcal{L}}_{w,l}=\\ \alpha \sum _{i=1}^{|\mathbb{V}|}\sum _{j=1}^{|\mathbb{V}|}(A_{i,j}^{w,w}\log \sigma ({\overrightarrow{\mathbf{x}}}_i^{w,w}\cdot {\overrightarrow{\mathbf{y}}}_j^{w,w})+b\frac{d_{i,\cdot }^{w,w}{d}_{i,\cdot }^{w,w}}{{\text{vol}}_G^{w,w}}\log \sigma ({\mathbf{-}\overrightarrow{\mathbf{x}}}_i^{w,w}\cdot {\overrightarrow{\mathbf{y}}}_j^{w,w}))\\ +\beta \sum _{i=1}^{|\mathbb{V}|}\sum _{j=1}^{|\mathbb{D}|}(A_{i,j}^{w,d}\log (\sigma ({\overrightarrow{\mathbf{x}}}_i^{w,d}\cdot {\overrightarrow{\mathbf{y}}}_j^{w,d})+b\frac{d_i^{w,d}{d}_j^{w,d}}{{\text{vol}}_G^{w,d}}\log \sigma ({\mathbf{-}\overrightarrow{\mathbf{x}}}_i^{w,d}\cdot {\overrightarrow{\mathbf{y}}}_j^{w,d}))\\ +\gamma \sum _{i=1}^{|\mathbb{V}|}\sum _{j=1}^{|\mathbb{L}|}(A_{i,j}^{w,l}\log \sigma ({\overrightarrow{\mathbf{x}}}_i^{w,l}\cdot {\overrightarrow{\mathbf{y}}}_j^{w,l})+b\frac{d_i^{w,l}{d}_j^{w,l}}{{\text{vol}}_G^{w,l}}\log \sigma ({\mathbf{-}\overrightarrow{\mathbf{x}}}_i^{w,l}\cdot {\overrightarrow{\mathbf{y}}}_j^{w,l}))\end{array}$$

   其中 $(\cdot {)}^{w,w},(\cdot {)}^{w,d},(\cdot {)}^{w,l}$$(\cdot)^{w,w},(\cdot)^{w,d},(\cdot)^{w,l}$ 分别为三个子网中的量，$\alpha ,\beta ,\gamma$$\alpha,\beta,\gamma$ 为三个超参数来平衡不同子网的损失，$b$$b$ 为负采样系数。根据 PTE 论文， $\alpha ,\beta ,\gamma$$\alpha,\beta,\gamma$ 需要满足：$\alpha {\text{vol}}_{G_{w,w}}=\beta {\text{vol}}_{G_{w,d}}=\gamma {\text{vol}}_{G_{w,l}}$$\alpha \text{vol}_{G_{w,w}} = \beta \text{vol}_{G_{w,d}} = \gamma \text{vol}_{G_{w,l}}$ ，这是因为PTE 在训练期间执行边采样，其中边是从三个子网中交替采样得到。

   根据前面的结论有：

   $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_i^{w,w}\cdot {\overrightarrow{\mathbf{y}}}_j^{w,w}=\log \left(\frac{{\text{vol}}_G^{w,w}{A}_{i,j}^{w,w}}{b{d}_i^{w,w}{d}_j^{w,w}}\right)\\ {\overrightarrow{\mathbf{x}}}_i^{w,d}\cdot {\overrightarrow{\mathbf{y}}}_j^{w,d}=\log \left(\frac{{\text{vol}}_G^{w,d}{A}_{i,j}^{w,d}}{b{d}_i^{w,d}{d}_j^{w,d}}\right)\\ {\overrightarrow{\mathbf{x}}}_i^{w,l}\cdot {\overrightarrow{\mathbf{y}}}_j^{w,l}=\log \left(\frac{{\text{vol}}_G^{w,l}{A}_{i,j}^{w,l}}{b{d}_i^{w,l}{d}_j^{w,l}}\right)\end{array}$$

   令：

   $$\begin{array}{c}\mathbf{X}=\left[\begin{array}{ccc}({\overrightarrow{\mathbf{x}}}_1^{w,w}{)}^{\mathrm{\top }}& \mathbf{0}& \mathbf{0}\\ ⋮& ⋮& ⋮\\ ({\overrightarrow{\mathbf{x}}}_{|\mathbb{V}|}^{w,w}{)}^{\mathrm{\top }}& \mathbf{0}& \mathbf{0}\\ \mathbf{0}& ({\overrightarrow{\mathbf{x}}}_1^{w,d}{)}^{\mathrm{\top }}& \mathbf{0}\\ ⋮& ⋮& ⋮\\ \mathbf{0}& ({\overrightarrow{\mathbf{x}}}_{|\mathbb{V}|}^{w,d}{)}^{\mathrm{\top }}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& ({\overrightarrow{\mathbf{x}}}_1^{w,l}{)}^{\mathrm{\top }}\\ ⋮& ⋮& ⋮\\ \mathbf{0}& \mathbf{0}& ({\overrightarrow{\mathbf{x}}}_{|\mathbb{V}|}^{w,l}{)}^{\mathrm{\top }}\end{array}\right]\mathbf{Y}=\left[\begin{array}{ccc}({\overrightarrow{\mathbf{y}}}_1^{w,w}{)}^{\mathrm{\top }}& \mathbf{0}& \mathbf{0}\\ ⋮& ⋮& ⋮\\ ({\overrightarrow{\mathbf{y}}}_{|\mathbb{V}|}^{w,w}{)}^{\mathrm{\top }}& \mathbf{0}& \mathbf{0}\\ \mathbf{0}& ({\overrightarrow{\mathbf{y}}}_1^{w,d}{)}^{\mathrm{\top }}& \mathbf{0}\\ ⋮& ⋮& ⋮\\ \mathbf{0}& ({\overrightarrow{\mathbf{y}}}_{|\mathbb{D}|}^{w,d}{)}^{\mathrm{\top }}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& ({\overrightarrow{\mathbf{y}}}_1^{w,l}{)}^{\mathrm{\top }}\\ ⋮& ⋮& ⋮\\ \mathbf{0}& \mathbf{0}& ({\overrightarrow{\mathbf{y}}}_{|\mathbb{L}|}^{w,l}{)}^{\mathrm{\top }}\end{array}\right]\end{array}$$

   则有 $\mathbf{X}\in {\mathbb{R}}^{3|\mathbb{V}|\times 3d},\mathbf{Y}\in {\mathbb{R}}^{(|\mathbb{V}|+|\mathbb{D}|+|\mathbb{L}|)\times 3d}$$\mathbf X \in \mathbb R^{3|\mathbb V|\times 3d},\mathbf Y \in \mathbb R^{(|\mathbb V|+|\mathbb D| +|\mathbb L|)\times 3d}$，且有：

   $$\begin{array}{c}{\mathbf{M}}_1=\alpha {\text{vol}}_{G_{w,w}}\mathbf{(}{\mathbf{D}}_{row}^{w,w}{)}^{-1}{\mathbf{A}}^{w,w}({\mathbf{D}}_{col}^{w,w}{)}^{-1}\\ {\mathbf{M}}_2=\beta {\text{vol}}_{G_{d,w}}\mathbf{(}{\mathbf{D}}_{row}^{d,w}{)}^{-1}{\mathbf{A}}^{d,w}({\mathbf{D}}_{col}^{d,w}{)}^{-1}\\ {\mathbf{M}}_3=\gamma {\text{vol}}_{G_{l,w}}\mathbf{(}{\mathbf{D}}_{row}^{l,w}{)}^{-1}{\mathbf{A}}^{l,w}({\mathbf{D}}_{col}^{l,w}{)}^{-1}\\ \mathbf{X}{\mathbf{Y}}^{\mathrm{\top }}=\log \left(\left[\begin{array}{ccc}{\mathbf{M}}_1& \mathbf{0}& \mathbf{0}\\ \mathbf{0}& {\mathbf{M}}_2& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& {\mathbf{M}}_3\end{array}\right]\right)-(\log b)\mathbf{I}\end{array}$$

1.1.3 DeepWalk

1. DeepWalk 首先通过在图上执行随机游走来产生一个 corpus $\mathcal{D}$$\mathcal D$ ，然后在 $\mathcal{D}$$\mathcal D$ 上训练 SkipGram 模型。这里我们重点讨论带负采样的 SkipGram 模型（skipgram with negative sampling: SGNS ）。整体算法如下所示：

   • 输入：

     • 图 $G(V,E,\mathbf{A})$$G(V,E,\mathbf A)$

     • 窗口大小 $T$$T$

     • 随机游走序列长度 $L$$L$

     • 总的随机游走序列数量 $N$$N$

   • 输出：顶点的 embedding 矩阵 $\mathbf{X}$$\mathbf X$

   • 算法步骤：

     • 迭代： $\text{for}s=1,2,\cdots ,N$$\text{for}\; s = 1,2,\cdots,N$ ，迭代过程为：

       • 根据先验概率分布 $P(w)$$P(w)$ 随机选择一个初始顶点 $w_1^{<s>}$$w^{<s>}_1$ 。

       • 在图 $G$$G$ 上从初始顶点 $w_1^{<s>}$$w^{<s>}_1$ 开始随机游走，采样得到一条长度为 $L$$L$ 的顶点序列 $(w_1^{<s>},\cdots ,w_L^{<s>})$$(w_1^{<s>},\cdots,w_L^{<s>})$ 。

       • 统计顶点共现关系。对于窗口位置 $j=1,2,\cdots ,L-T$$j=1,2,\cdots,L-T$ ：

         • 考虑窗口内第 $r$$r$ 个顶点 $r=1,2,\cdots ,T$$r=1,2,\cdots,T$ ：

           • 添加 vertex-context 顶点对 $(w_j^{<s>},w_{j+r}^{<s>})$$(w_j^{<s>},w_{j+r}^{<s>})$ 到 $\mathcal{D}$$\mathcal D$ 中。

           • 添加 vertex-context 顶点对 $(w_{j+r}^{<s>},w_j^{<s>})$$(w_{j+r} ^{<s>},w_{j}^{<s>})$ 到 $\mathcal{D}$$\mathcal D$ 中。

     • 然后在 $\mathcal{D}$$\mathcal D$ 上执行负采样系数为 $b$$b$ 的 SGNS 。

2. 根据论文 《Neural Word Embedding as Implicit Matrix Factorization》 ， SGNS 等价于隐式的矩阵分解：

   $$\begin{array}{c}\mathbf{X}{\mathbf{Y}}^{\mathrm{\top }}=\mathbf{M}\\ M_{w,c}=\log \left(\frac{n(w,c)\times |\mathcal{D}|}{n(w)\times n(c)}\right)-\log b\end{array}$$

   其中：$|\mathcal{D}|$$|\mathcal D|$ 为语料库大小； $n(w,c)$$n(w,c)$ 为语料库 $\mathcal{D}$$\mathcal D$ 中vertex-context $(w,c)$$(w,c)$ 共现的次数；$n(w)$$n(w)$ 为语料库中 vertex $w$$w$ 出现的总次数； $n(c)$$n(c)$ 为语料库中 context $c$$c$ 出现的总次数；$b$$b$ 为负采样系数。

   这个矩阵 $\mathbf{M}$$\mathbf M$ 刻画了图结构的什么属性？目前并没有相关的分析工作。此外，这里是否可以去掉 log、是否可以去掉 log b ，也没有理论的解释。

3. 接下来的分析依赖于一些关键的假设：

   • 假设图 $G$$G$ 为无向的（undirected）、连接的（connected）、（non-bipartite ）的，这使得 $P(w)=d_w/{\text{vol}}_G$$P(w) = d_w/\text{vol}_G$ 为一个平稳分布。

   • 假设每个随机游走序列的第一个顶点从这个平稳分布 $P(w)$$P(w)$ 中随机选取。

   对于 $r=1,2,\cdots ,T$$r=1,2,\cdots,T$ ，定义：

   • ${\mathcal{D}}_{r\to }=\{(w,c)\mid (w,c)\in \mathcal{D},w=w_j^{<s>},c=w_{j+r}^{<s>}\}$$\mathcal D_{r\rightarrow} = \{(w,c)\mid (w,c)\in \mathcal D, w = w_j^{<s>},c = w_{j+r}^{<s>}\}$ ，即 ${\mathcal{D}}_{r\to }$$\mathcal D_{r\rightarrow}$ 为 $\mathcal{D}$$\mathcal D$ 的子集，它的每个 context 顶点 $c$$c$ 都在每个 vertex 顶点 $w$$w$ 的右侧 $r$$r$ 步。另外定义 $n(w,c{)}_{r\to }$$n(w,c)_{r\rightarrow}$ 为 ${\mathcal{D}}_{r\to }$$\mathcal D_{r\rightarrow}$ 中vertex-context $(w,c)$$(w,c)$ 共现的次数。

   • ${\mathcal{D}}_{r\leftarrow }=\{(w,c)\mid (w,c)\in \mathcal{D},w=w_{j+r}^{<s>},c=w_j^{<s>}\}$$\mathcal D_{r\leftarrow} = \{(w,c)\mid (w,c)\in \mathcal D, w = w_{j+r}^{<s>},c = w_{j}^{<s>}\}$ ， 即 ${\mathcal{D}}_{r\to }$$\mathcal D_{r\rightarrow}$ 为 $\mathcal{D}$$\mathcal D$ 的子集，它的每个 context 顶点 $c$$c$ 都在每个 vertex 顶点 $w$$w$ 的左侧 $r$$r$ 步。另外定义 $n(w,c{)}_{r\leftarrow }$$n(w,c)_{r\leftarrow}$ 为 ${\mathcal{D}}_{r\leftarrow }$$\mathcal D_{r\leftarrow}$ 中vertex-context $(w,c)$$(w,c)$ 共现的次数。

   • 定义 $\mathbf{P}={\mathbf{D}}^{-1}\mathbf{A}$$\mathbf P = \mathbf D^{-1}\mathbf A$ ，${\mathbf{P}}^r=\underset{r}{\underbrace{\mathbf{P}\times \cdots \times \mathbf{P}}}$$\mathbf P^r = \underbrace {\mathbf P\times \cdots \times \mathbf P}_r$ （$r$$r$ 个 $\mathbf{P}$$\mathbf P$ 相乘），其中对角矩阵 $\mathbf{D}=\text{diag}(d_1,\cdots ,d_{|V|})$$\mathbf D = \text{diag}(d_1,\cdots,d_{|V|})$，$d_w=\sum _c{A}_{w,c}$$d_w = \sum_{c}A_{w,c}$ ，${\text{vol}}_G=\sum _w\sum _c{A}_{w,c}$$\text{vol}_G=\sum_{w}\sum_{c}A_{w,c}$。定义 $P_{w,c}^r$$P^r_{w,c}$ 为 ${\mathbf{P}}^r$$\mathbf P^r$ 的第 $w$$w$ 行、第 $c$$c$ 列。

     事实上 $\mathbf{P}$$\mathbf P$ 定义了一个概率转移矩阵， $P_{w,c}$$P_{w,c}$ 定义了从顶点 $w$$w$ 经过一步转移到 $c$$c$ 的概率；$P_{w,c}^r$$P^r_{w,c}$ 定义了从顶点 $w$$w$ 经过 $r$$r$ 步转移到 $c$$c$ 的概率。

   另外考虑到对称性，我们有 $\mathbf{A}={\mathbf{A}}^{\mathrm{\top }}$$\mathbf A= \mathbf A^{\top}$ 。

4. 定理一：定义，则当 $L\to \mathrm{\infty }$$L\rightarrow \infty$ 时有：

   $$\begin{array}{c}\frac{n(w,c{)}_{r\to }}{|{\mathcal{D}}_{r\to }|}\stackrel{p}{\to }\frac{d_w}{{\text{vol}}_G}{P}_{w,c}^r\\ \frac{n(w,c{)}_{r\leftarrow }}{|{\mathcal{D}}_{r\leftarrow }|}\stackrel{p}{\to }\frac{d_c}{{\text{vol}}_G}{P}_{c,w}^r\end{array}$$

   其中：$\stackrel{p}{\to }$$\stackrel{p}{\rightarrow}$ 表述依概率收敛。

   证明：

   首先介绍 S.N. Bernstein 大数定律：设 $Y_1,Y_2,\cdots$$Y_1,Y_2,\cdots$ 为一个随机变量的序列，其中每个随机变量具有有限的期望 $\mathbb{E}[Y_j]<K$$\mathbb E[Y_j]\lt K$ 和有限的方差 $\text{Var}(Y_j)<K$$\text{Var} (Y_j) \lt K$ ，并且协方差满足：当 $|i-j|\to \mathrm{\infty }$$|i-j|\rightarrow \infty$ 时，$\text{Cov}(Y_i,Y_j)\to 0$$\text{Cov}(Y_i,Y_j)\rightarrow 0$ 。则大数定律（ law of large numbers:LLN ）成立。

   考虑只有一条随机游走序列（即 $N=1$$N=1$ ）：$(w_1,\cdots ,w_L)$$(w_1,\cdots,w_L)$ 。给定一个 vertex-context $(w,c)$$(w,c)$ ，定义随机变量 $Y_j,j=1,2,\cdots ,L-T$$Y_j,j=1,2,\cdots,L-T$ 为事件 $w_j=w,w_{j+r}=c$$w_j=w,w_{j+r} = c$ 发生的指示器（ indicator ）。

   我们观察到：

   • $|{\mathcal{D}}_{r\to }|=L-T$$|\mathcal D_{r\rightarrow}| = L-T$，$\sum _{j=1}^{L-T}{Y}_j=n(w,c{)}_{r\to }$$\sum_{j=1}^{L-T} Y_j = n(w,c)_{r\rightarrow}$ 。因此有：

     $$\frac{n(w,c{)}_{r\to }}{|{\mathcal{D}}_{r\to }|}=\frac{1}{L-T}\sum _{j=1}^{L-T}{Y}_j$$

   • 基于我们对图的假设和随机游走的假设，则有：$Y_j$$Y_j$ 发生的概率等于 $w_j=w$$w_j=w$ 的概率乘以 $w$$w$ 经过 $r$$r$ 步转移到 $c$$c$ 的概率。即：

     $$\mathbb{E}[Y_j]=P(Y_j)=\frac{d_w}{{\text{vol}}_G}\times P_{w,c}^r$$

   • 基于我们对图的假设和随机游走的假设，则有：当 $j>i+r$$j\gt i+r$ 时有：

     $$\begin{array}{c}\mathbb{E}[Y_i{Y}_j]=P(w_i=w,w_{i+r}=c,w_j=w,w_{j+r}=c)\\ =\frac{d_w}{{\text{vol}}_G}{P}_{w,c}^r\times P_{c,w}^{j-i-r}\times P_{w,c}^r\end{array}$$

     其中：第一项为 $w_i$$w_i$ 采样到 $w$$w$ 的概率；第二项为从 $w$$w$ 经过 $r$$r$ 步转移到 $c$$c$ 的概率；第三项为从 $c$$c$ 经过 $j-(r+i)$$j-(r+i)$ 步转移到 $w$$w$ 得概率；第四项为从 $w$$w$ 经过 $r$$r$ 步转移到 $c$$c$ 的概率。

   则有：

   $$\text{Cov}(Y_i,Y_j)=\mathbb{E}[Y_i{Y}_j]-\mathbb{E}[Y_i]\mathbb{E}[Y_j]=\frac{d_w}{{\text{vol}}_G}{P}_{w,c}^r[P_{c,w}^{j-i-r}-\frac{d_w}{{\text{vol}}_G}]P_{w,c}^r$$

   当 $|j-i|\to \mathrm{\infty }$$|j-i|\rightarrow \infty$ 时，从 $c$$c$ 经过 $\mathrm{\infty }$$\infty$ 步转移到 $w$$w$ 的概率收敛到它的平稳分布，即 $p(w_j=w)$$p(w_j=w)$ 。即：

   $$\underset{|j-i|\to \mathrm{\infty }}{lim}{P}_{c,w}^{j-i-r}=\frac{d_w}{{\text{vol}}_G}$$

   因此有 $\underset{|j-i|\to \mathrm{\infty }}{lim}\text{Cov}(Y_i,Y_j)=0$$\lim_{|j- i|\rightarrow \infty} \text{Cov}(Y_i,Y_j) = 0$ 。因此随机游走序列收敛到它的平稳分布。

   应用大数定律，则有：

   $$\frac{n(w,c{)}_{r\to }}{|{\mathcal{D}}_{r\to }|}=\frac{1}{L-T}\sum _{j=1}^{L-T}{Y}_j\stackrel{p}{\to }\frac{1}{L-T}\sum _{j=1}^{L-T}\mathbb{E}[Y_j]=\frac{d_w}{{\text{vol}}_G}{P}_{w,c}^r$$

   类似地，我们有：

   $$\frac{n(w,c{)}_{r\leftarrow }}{|{\mathcal{D}}_{r\leftarrow }|}=\frac{d_c}{{\text{vol}}_G}{P}_{c,w}^r$$

   当 $N>1$$N\gt 1$ 时，我们定义 $Y_j^{<s>},s=1,2,\cdots ,N,j=1,2,\cdots ,L-T$$Y_j^{<s>},s=1,2,\cdots,N,j=1,2,\cdots,L-T$ 为事件 $w_j^{<s>}=w,w_{j+r}^{(s)}=c$$w_j^{<s>} = w, w_{j+r}^{(s)} = c$ 的指示器，同样可以证明相同的结论。

5. 事实上如果随机游走序列的初始顶点分布使用其它分布（如均匀分布），则可以证明：当 $j\to \mathrm{\infty }$$j\rightarrow \infty$ 时，有：

   $$\underset{j\to \mathrm{\infty }}{lim}P(w_j=w,w_{j+r}=c)=\frac{d_w}{{\text{vol}}_G}{P}_{w,c}^r$$

   因此定理一仍然成立。

6. 定理二：当 $L\to \mathrm{\infty }$$L\rightarrow\infty$ 时，有：

   $$\frac{n(w,c)}{|\mathcal{D}|}\stackrel{p}{\to }\frac{1}{2T}\sum _{r=1}^T(\frac{d_w}{{\text{vol}}_G}{P}_{w,c}^r+\frac{d_c}{{\text{vol}}_G}{P}_{c,w}^r)$$

   证明：

   注意到 $\frac{|{\mathcal{D}}_{r\to }|}{|\mathcal{D}|}=\frac{|{\mathcal{D}}_{r\leftarrow }|}{|\mathcal{D}|}=\frac{1}{2T}$$\frac{|\mathcal D_{r\rightarrow}|}{|\mathcal D|}=\frac{|\mathcal D_{r\leftarrow}|}{|\mathcal D|} = \frac{1}{2T}$ ，应用定理一有：

   $$\begin{array}{c}\frac{n(w,c)}{|\mathcal{D}|}=\frac{\sum _{r=1}^T(n(w,c{)}_{r\to }+n(w,c{)}_{r\leftarrow })}{\sum _{r=1}^T(|{\mathcal{D}}_{r\to }|+|{\mathcal{D}}_{r\leftarrow }|)}=\frac{1}{2T}\sum _{r=1}^T(\frac{n(w,c{)}_{r\to }}{|{\mathcal{D}}_{r\to }|}+\frac{n(w,c{)}_{r\leftarrow }}{|{\mathcal{D}}_{r\leftarrow }|})\\ \stackrel{p}{\to }\frac{1}{2T}\sum _{r=1}^T(\frac{d_w}{{\text{vol}}_G}{P}_{w,c}^r+\frac{d_c}{{\text{vol}}_G}{P}_{c,w}^r)\end{array}$$

   进一步的，考察 $w$$w$ 的边际分布和 $c$$c$ 的边际分布，当 $L\to \mathrm{\infty }$$L\rightarrow \infty$ 时，我们有：

   $$\frac{n(w)}{|\mathcal{D}|}\stackrel{p}{\to }\frac{d_w}{{\text{vol}}_G},\frac{n(c)}{|\mathcal{D}|}\stackrel{p}{\to }\frac{d_c}{{\text{vol}}_G}$$

   当 $r$$r$ 不大时，单边的、间隔 $r$$r$ 的 vertex-context 数量是固定的，为全体 vertex-context 数量的 $1/(2T)$$1/(2T)$ 。

7. 定理三：在 DeepWalk 中，当 $L\to \mathrm{\infty }$$L\rightarrow \infty$ 时有：

   $$\frac{n(w,c)|\mathcal{D}|}{n(w)n(c)}\stackrel{p}{\to }\frac{{\text{vol}}_G}{2T}(\frac{1}{d_c}\sum _{i=1}^T{P}_{w,c}^r+\frac{1}{d_w}\sum _{i=1}^T{P}_{c,w}^r)$$

   因此DeepWalk 等价于因子分解：

   $$\mathbf{X}{\mathbf{Y}}^{\mathrm{\top }}=\log \left(\frac{{\text{vol}}_G}{T}\left(\sum _{r=1}^T{\mathbf{P}}^r\right){\mathbf{D}}^{-1}\right)-(\log b)\mathbf{I}$$

   证明：

   利用定理二和continous mapping theorem，有：

   $$\begin{array}{c}\frac{n(w,c)|\mathcal{D}|}{n(w)n(c)}=\frac{\frac{n(w,c)}{|\mathcal{D}|}}{\frac{n(w)}{|\mathcal{D}|}\frac{n(c)}{|\mathcal{D}|}}\stackrel{p}{\to }\frac{\frac{1}{2T}\sum _{r=1}^T(\frac{d_w}{{\text{vol}}_G}{P}_{w,c}^r+\frac{d_c}{{\text{vol}}_G}{P}_{c,w}^r)}{\frac{d_w}{{\text{vol}}_G}\times \frac{d_c}{{\text{vol}}_G}}\\ =\frac{{\text{vol}}_G}{2T}(\frac{1}{d_c}\sum _{r=1}^T{P}_{w,c}^r+\frac{1}{d_w}\sum _{r=1}^T{P}_{c,w}^r)\end{array}$$

   写成矩阵的形式为：

   $$\begin{array}{c}\frac{{\text{vol}}_G}{2T}(\sum _{r=1}^T{\mathbf{P}}^r{\mathbf{D}}^{-1}+\sum _{r=1}^T{\mathbf{D}}^{-1}({\mathbf{P}}^r{)}^{\mathrm{\top }})\\ =\frac{{\text{vol}}_G}{2T}(\sum _{r=1}^T(\underset{r}{\underbrace{{\mathbf{D}}^{-1}\mathbf{A}\times \cdots \times {\mathbf{D}}^{-1}\mathbf{A}}}){\mathbf{D}}^{-1}+\sum _{r=1}^T{\mathbf{D}}^{-1}(\underset{r}{\underbrace{\mathbf{A}{\mathbf{D}}^{-1}\times \cdots \times \mathbf{A}{\mathbf{D}}^{-1}}}))\\ =\frac{{\text{vol}}_G}{T}(\sum _{r=1}^T(\underset{r}{\underbrace{{\mathbf{D}}^{-1}\mathbf{A}\times \cdots \times {\mathbf{D}}^{-1}\mathbf{A}}}){\mathbf{D}}^{-1})=\frac{{\text{vol}}_G}{T}\left(\sum _{r=1}^T{\mathbf{P}}^r\right){\mathbf{D}}^{-1}\end{array}$$

8. 事实上我们发现，当 $T=1$$T=1$ 时，DeepWalk 就成为了 LINE(2nd)， 因此 LINE(2nd) 是 DeepWalk 的一个特例。

1.1.4 node2vec

1. node2vec 是最近提出的 graph embedding 方法，其算法如下：

   • 输入：

     • 图 $G(V,E,\mathbf{A})$$G(V,E,\mathbf A)$

     • 窗口大小 $T$$T$

     • 随机游走序列长度 $L$$L$

     • 总的随机游走序列数量 $N$$N$

   • 输出：顶点

   • 算法步骤：

     • 构建转移概率张量 $\mathbf{P}\in {\mathbb{R}}^{|V|\times |V|\times |V|}$$\mathbf P\in \mathbb R^{|V| \times |V|\times |V|}$

     • 迭代： $\text{for}s=1,2,\cdots ,N$$\text{for}\; s = 1,2,\cdots,N$ ，迭代过程为：

       • 根据先验概率分布 $Q(w_1,w_2)$$Q(w_1,w_2)$ 随机选择初始的两个顶点 $(w_1^{<s>},w_2^{<s>})$$(w^{<s>}_1,w_2^{<s>})$ 。

       • 在图 $G$$G$ 上从初始顶点 $w_1^{<s>},w_2^{<s>}$$w^{<s>}_1,w^{<s>}_2$ 开始二阶随机游走，采样得到一条长度为 $L$$L$ 的顶点序列 $(w_1^{<s>},\cdots ,w_L^{<s>})$$(w_1^{<s>},\cdots,w_L^{<s>})$ 。

       • 统计顶点共现关系。对于窗口位置 $j=2,\cdots ,L-T$$j=2,\cdots,L-T$ ：

         • 考虑窗口内第 $r$$r$ 个顶点 $r=1,2,\cdots ,T$$r=1,2,\cdots,T$ ：

           • 添加三元组 $(w_j^{<s>},w_{j+r}^{<s>},w_{j-1}^{<s>})$$(w_j^{<s>},w_{j+r}^{<s>},w_{j-1}^{<s>})$ 到 $\mathcal{D}$$\mathcal D$ 中。

           • 添加三元组 $(w_{j+r}^{<s>},w_j^{<s>},w_{j-1}^{<s>})$$(w_{j+r} ^{<s>},w_{j}^{<s>},w_{j-1}^{<s>})$ 到 $\mathcal{D}$$\mathcal D$ 中。

     • 然后在 ${\mathcal{D}}^{\prime }=\{(w,c)\mid (w,c,u)\in \mathcal{D}\}$$\mathcal D^\prime=\{(w,c)\mid (w,c,u)\in \mathcal D \}$ 上执行负采样系数为 $b$$b$ 的 SGNS 。

     注意：这里为了方便分析，我们使用三元组 $(w_j,w_{j+r},w_{j-1})$$(w_j,w_{j+r},w_{j-1})$ ，而不是vertex-context 二元组。

2. node2vec 的转移概率张量 $\mathbf{P}$$\mathbf P$ 采取如下的方式定义：

   • 首先定义未归一化的概率：

     $$\begin{array}{c}{\hat{P}}_{w,v,u}=\{\begin{array}{ll}\frac{1}{p},& (u,v)\in E,(v,w)\in E,u=w\\ 1,& (u,v)\in E,(v,w)\in E,u\ne w,(w,u)\in E\\ \frac{1}{q},& (u,v)\in E,(v,w)\in E,u\ne w,(w,u)\notin E\\ 0,& \text{else}\end{array}\end{array}$$

     其中 ${\hat{P}}_{w,v,u}$$\hat P_{w,v,u}$ 表示在 $w_{j-1}=u,w_j=v$$w_{j-1}=u,w_j = v$ 的条件下，$w_{j+1}=w$$w_{j+1} = w$ 的概率。

   • 然后得到归一化的概率：

     $$P_{w,v,u}=P(w_{j+1}=w\mid w_j=v,w_{j-1}=u)=\frac{{\hat{P}}_{w,v,u}}{\sum _{u^{\prime }}{\hat{P}}_{w,v,u^{\prime }}}$$

3. 类似 DeepWalk ，我们定义：

   $$\begin{array}{c}{\mathcal{D}}_{r\to }=\{(w,c,u)\mid (w,c,u)\in \mathcal{D},w_j^n=w,w_{j+r}^n=c,w_{j-1}^n=u\}\\ {\mathcal{D}}_{r\leftarrow }=\{(w,c,u)\mid (w,c,u)\in \mathcal{D},w_{j+r}^n=w,w_j^n=c,w_{j-1}^n=u\}\end{array}$$

   这里 $u$$u$ 为previous 顶点。

   定义 $n(w,c,u{)}_{\to }$$n(w,c,u)_{\rightarrow}$ 为 $(w,c,u)$$(w,c,u)$ 出现在 ${\mathcal{D}}_{r\to }$$\mathcal D_{r\rightarrow}$ 中出现的次数；定义 $n(w,c,u{)}_{\leftarrow }$$n(w,c,u)_{\leftarrow}$ 为 $(w,c,u)$$(w,c,u)$ 出现在 ${\mathcal{D}}_{r\leftarrow }$$\mathcal D_{r\leftarrow}$ 中出现的次数。

   定义二阶随机游走序列的平稳分布为 $\mathbf{Q}$$\mathbf Q$，它满足：$\sum _u{P}_{w,v,u}{Q}_{v,u}=Q_{w,v}$$\sum_{u} P_{w,v,u}Q_{v,u} = Q_{w,v}$ 。根据 Perron-Frobenius 定理，这个平稳分布一定存在。为了便于讨论，我们定义每个随机游走序列的初始两个顶点服从平稳分布 $\mathbf{Q}$$\mathbf Q$ 。

   定义高阶转移概率矩阵 $P_{w,v,u}^r=P(w_{j+r}=w\mid w_j=v,w_{j-1}=u)$$P^r_{w,v,u} = P(w_{j+r}=w\mid w_j=v,w_{j-1}=u)$ 。

   由于篇幅有限，这里给出 node2vec 的主要结论，其证明过程类似 DeepWalk ：

   $$\begin{array}{c}\frac{n(w,c,u{)}_{r\to }}{|{\mathcal{D}}_{r\to }|}\stackrel{p}{\to }{Q}_{w,u}{P}_{c,w,u}^r,\frac{n(w,c,u{)}_{r\leftarrow }}{|{\mathcal{D}}_{r\leftarrow }|}\stackrel{p}{\to }{Q}_{c,u}{P}_{w,c,u}^r\\ \frac{n(w,c{)}_{r\to }}{|{\mathcal{D}}_{r\to }|}=\frac{\sum _{u}n(w,c,u{)}_{r\to }}{|{\mathcal{D}}_{r\to }|}\stackrel{p}{\to }\sum _u{Q}_{w,u}{P}_{c,w,u}^r\\ \frac{n(w,c{)}_{r\leftarrow }}{|{\mathcal{D}}_{r\leftarrow }|}=\frac{\sum _{u}n(w,c,u{)}_{r\leftarrow }}{|{\mathcal{D}}_{r\leftarrow }|}\stackrel{p}{\to }\sum _u{Q}_{c,u}{P}_{w,c,u}^r\\ \frac{n(w,c)}{|\mathcal{D}|}\stackrel{p}{\to }\frac{1}{2T}\sum _{r=1}^T(\sum _u{Q}_{w,u}{P}_{c,w,u}^r+\sum _u{Q}_{c,u}{P}_{w,c,u}^r)\\ \frac{n(w)}{|\mathcal{D}|}\stackrel{p}{\to }\sum _u{Q}_{w,u},\frac{n(c)}{|\mathcal{D}|}\stackrel{p}{\to }\sum _u{Q}_{c,u}\end{array}$$

   因此 node2vec 有：

   $$\frac{n(w,c)\times |\mathcal{D}|}{n(w)\times n(c)}\stackrel{p}{\to }\frac{\frac{1}{2T}\sum _{r=1}^T(\sum _u{Q}_{w,u}{P}_{c,w,u}^r+\sum _u{Q}_{c,u}{P}_{w,c,u}^r)}{\left(\sum _u{Q}_{w,u}\right)\times \left(\sum _u{Q}_{c,u}\right)}$$

   尽管实现了 node2vec 的封闭形式，我们将其矩阵形式的公式留待以后研究。

4. 注意：存储和计算转移概率张量 ${\mathbf{P}}^r$$\mathbf P^r$ 以及对应的平稳分布代价非常高，使得我们难以对完整的二阶随机游走动力学过程建模。但是最近的一些研究试图通过对 $\mathbf{Q}$$\mathbf Q$ 进行低秩分解来降低时间复杂度和空间复杂度：

   $$Q_{u,v}={\overrightarrow{\mathbf{q}}}_u\cdot {\overrightarrow{\mathbf{q}}}_v$$

   由于篇幅限制，我们这里主要集中在一阶随机游走框架DeepWalk 上。